/*******************************************************/
/* Aluno: Luciano G. S. Ramalho                        */
/* Numero USP: 1002101                                 */
/* Exercicio-Programa 3 -- Compressao de Arquivos      */
/* MAC110 (BCC) -- 2007 -- Professor: Reverbel         */
/* Compilador: gcc (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5) */
/*******************************************************/

#include <stdio.h>
#include <string.h>

#define SUCESSO     0
#define FALHA       -1
#define DESISTENCIA -999

#define TAM_DIC     255

#define DEBUG       1
#define NOME_PARES  "lz77-pares.txt"

int abrir_arquivo(FILE **arq, char *modo, char *msg);
void codifica(unsigned char buffer[],
              int pos_ini, int pos_ult, int *dist, int *compr);
void deslocar(unsigned char buffer[], int delta);
int comprimir(FILE *entrada, FILE *saida, unsigned char buffer[]);
int descomprimir(FILE *entrada, FILE *saida, unsigned char buffer[]);

int main ()
{
    int resultado;  /* resultado de uma chamada de funcao */
    char op[3];     /* opcao: "1"-compressao, "2"-descompressao */
    FILE *entrada = NULL;   /* arquivo de entrada */
    FILE *saida = NULL;     /* arquivo de saida */

    unsigned char buffer[TAM_DIC*2];
                              
    op[0] = 0;
    while ((op[0] != '1') && (op[0] != '2')) {
        printf("[1] compressao; [2] descompressao - escolha a operacao: ");
        fgets(op, sizeof(op), stdin);
    }
    resultado = abrir_arquivo(&entrada, "rb", "nome do arquivo de entrada: ");
    if (resultado != SUCESSO) 
        return resultado;
    resultado = abrir_arquivo(&saida, "wb", "nome do arquivo de saida: ");
    if (resultado != SUCESSO) 
        return resultado;
    
    if (op[0] == '1') 
        resultado = comprimir(entrada, saida, buffer);
    else
        resultado = descomprimir(entrada, saida, buffer);

    fclose(entrada);
    fclose(saida);
    return resultado;
}

int abrir_arquivo(FILE **arq, char *modo, char *msg)
{
    char nome_arq[80];    /* nome do arquivo a abrir */
    while (*arq == NULL) {
        printf(msg);
        fgets(nome_arq, sizeof(nome_arq), stdin); /* ler nome de stdin */
        nome_arq[strlen(nome_arq)-1] = '\0'; /* eliminar \n */
        if (strlen(nome_arq) == 0)
            /* o usuário nao digitou um nome, vamos desistir */
            return DESISTENCIA;  
        *arq = fopen(nome_arq, modo);
        if (*arq == NULL) 
            /* nao foi possivel abrir o arquivo:
               em modo "r" provavelmente o arquivo nao existe,
               em modo "w" provavelmente o arquivo e' read-only;
               de qq. modo, vamos exibir uma mensagem de erro e
               deixar o usuario informar outro nome de arquivo
           */
            perror(nome_arq);
    }
    return SUCESSO;
}

void codifica(unsigned char buffer[], int pos_ini, int pos_ult, int *dist, int *compr)
{
    /* determina o par (dist, compr) para o próximo trecho a ser comprimido */
    int car_iguais;  /* num de cars iguais no dicionario e no look-ahead */
    int max_car_iguais = 0; /* num maximo de cars iguais encontrados */
    int pos_max = 0;        /* posicao em que foram encontrados os cars */
    int i;
    
    for (i = pos_ini; i < TAM_DIC; i++) {
        car_iguais = 0;
        while ((car_iguais < TAM_DIC) && ((TAM_DIC+car_iguais)<=pos_ult)
            && (buffer[i+car_iguais] == buffer[TAM_DIC+car_iguais])) 
            car_iguais++;
        
        /* Variante discutida no forum: registrar ocorrência de maior dist.
           Isso não altera eficiencia da compressao e nem muda a semantica da
           descompressao. Para fazer assim, o proximo if ficaria como segue:
        if (car_iguais > max_car_iguais) { */
        if (car_iguais >= max_car_iguais) {
            max_car_iguais = car_iguais;
            pos_max = i;
        }
    }
    /* Variante discutida em aula: codificar apenas repeticoes de 2 ou
       mais bytes para economizar trabalho na descompressao. Isso não altera
       a eficiencia da compressao e nem muda a semantica da descompressao.
       Para fazer assim, o proximo if ficaria como segue:
    if (max_car_iguais > 1) { */
    if (max_car_iguais > 0) {
        *dist = TAM_DIC-pos_max;
        *compr = max_car_iguais;
    } else {
        *dist = 0;
        *compr = buffer[TAM_DIC];
    }
}

void deslocar(unsigned char buffer[], int delta)
{
    /* desloca o buffer delta posicoes em direcao `a posicao 0 */
    int i;
    for (i=delta; i<(TAM_DIC*2); i++)
        buffer[i-delta]=buffer[i];    
}        

int comprimir(FILE *entrada, FILE *saida, unsigned char buffer[]) 
{
    /* le o arquivo de entrada, comprime e grava o de saida, usando o buffer */
    int pos_ini = TAM_DIC;        /* pos do primeiro caractere no dicionario */
    int pos_ult;        /* pos do ultimo caractere no look-ahead */
    int tam_ent = 0;    /* tamanho do arquivo de entrada */
    int tam_sai = 0;    /* tamanho do arquivo de saida */
    int res;            /* resultado da leitura do arquivo */
    int dist;           /* distancia ate ocorrencia anterior */
    int compr;          /* comprimento da ocorrencia repetida */
    double razao;       /* razao de compressao */

#ifdef DEBUG
    /* geracao do arquivo de pares */
    FILE *pares = NULL; /* arquivo de pares dist, compr */
    pares = fopen(NOME_PARES, "w");
    if (pares == NULL) 
        perror(NOME_PARES);
#endif

    /* preencher look-ahead */
    int i;
    for (i=0; i < TAM_DIC; i++) {
        res = fgetc(entrada);
        if (res != EOF) { 
            buffer[TAM_DIC+i] = (unsigned char)res;
            tam_ent++;
        } else {
            if (feof(entrada))  /* final do arquivo, parar de ler */
                break;
            else {              /* erro de E/S */
                perror("comprimir");
                return FALHA;
            }
        }
    }
    /* calcular posicao do ultimo byte valido no look-ahead */
    pos_ult = TAM_DIC + tam_ent - 1;
    
    while (pos_ult >= TAM_DIC) { 
        codifica(buffer, pos_ini, pos_ult, &dist, &compr);
#ifdef DEBUG
        /* gravacao do arquivo de pares */
        if (pares != NULL) { /* o arquivo esta aberto? */
            fprintf(pares,"%3d %3d ", dist, compr);
            if (dist != 0) {
                /* exibir os caracteres da sequencia entre aspas duplas */
                fprintf(pares,"\"");
                for (i=0; i<compr; i++)
                    if ((buffer[TAM_DIC+i]>=32) && (buffer[TAM_DIC+i]<127))
                        fprintf(pares,"%c",buffer[TAM_DIC+i]);
                    else
                        fprintf(pares,"\\x%02x",buffer[TAM_DIC+i]);
                fprintf(pares,"\"\n");
            }
            else
                /* exibir o caractere entre aspas simples */
                if ((compr>=32) && (compr<127))
                    fprintf(pares,"'%c'\n",(unsigned char)compr);
                else
                    fprintf(pares,"'\\x%02x'\n",(unsigned char)compr);
        }
#endif
        fputc(dist, saida);
        fputc(compr, saida);
        /* deslocar 1 pos qdo o car. não foi achado no dicicionario */
        if (dist == 0)
            compr = 1;
        deslocar(buffer, compr);
        pos_ini -= compr;
        if (pos_ini < 0) pos_ini = 0;
        tam_sai += 2;

        /* preencher look-ahead */
        for (i=compr; i>0; i--) {
            res = fgetc(entrada);
            if (res != EOF) { 
                buffer[TAM_DIC*2-i] = (unsigned char)res;
                tam_ent++;
            } else {
                if (feof(entrada))  /* nao tem mais bytes para ler */
                    pos_ult--;      /* encurtar look-ahead */
                else {              /* erro de I/O */
                    perror("comprimir,1"); /* reportar erro de E/S */
                    return FALHA;
                }
            }
        }   
    }

    razao = (tam_ent-tam_sai)/(float)tam_ent * 100.0;
    if (tam_sai > tam_ent) {
        fprintf(stderr, "AVISO: arquivo gerado ficou %.2f%% maior que o original.\n",-razao);
        printf("*EXPANSAO*: %6.2f%%\n", -razao);
    } else
        printf("compressao: %6.2f%%\n", razao);

#ifdef DEBUG
    if (pares != NULL) { /* o arquivo esta aberto? */
        fclose(pares);
        printf("arquivo "NOME_PARES" gravado.\n");
    }
#endif
    return SUCESSO;
}

int descomprimir(FILE *entrada, FILE *saida, unsigned char buffer[])
{
    /* le o arquivo de entrada, descomprime e grava na saida usando o buffer*/
    int dist = EOF;     /* distancia ate ocorrencia anterior */
    int compr = EOF;    /* comprimento da ocorrencia repetida */
    int tam_sai = 0;    /* tamanho do arquivo de saida */
    unsigned char car;  /* caractere lido */
    int i;
    
    /* repetir enquanto for possivel ler um par dist, compr */   
    while (((dist = fgetc(entrada)) != EOF) &&
           ((compr = fgetc(entrada)) != EOF)) {
        if (dist == 0) {
            /* gravar byte que acabou de ser lido */
            fputc(compr, saida);
            buffer[TAM_DIC] = (unsigned char)compr;
            compr = 1; /* para efeito do deslocamento */
        } else
            /* gravar compr bytes do dicionario */
            for (i=0; i<compr; i++) {
                car = buffer[TAM_DIC-dist+i];
                fputc(car, saida);
                buffer[TAM_DIC+i] = car;
            }
        deslocar(buffer, compr);
        tam_sai += compr;
    }
    /* se lemos dist mas nao compr, o arquvi esta' truncado */
    if ((dist != EOF) && (compr == EOF)) {
        fprintf(stderr,"ERRO: arquivo de entrada invalido (tamanho impar)");
        return FALHA;
    } else if (!feof(entrada)) { /*fgetc retornou EOF antes do final do arq.*/
        perror("descomprimir"); /* erro de E/S */
        return FALHA;
    }
    printf("%d bytes gravados\n", tam_sai);
    return SUCESSO;
}

